package pentago.engine;

import java.util.ArrayList;
import java.util.Hashtable;

import pentago.exceptions.PentagoInvalidPlatePositionException;
import pentago.exceptions.PentagoInvalidPositionException;
import pentago.exceptions.PentagoInvalidRotationException;

public class TTAlphaBetaAlgorithm implements IPentagoAlgorithm {

    // private Hashtable currentStates;
    private ArrayList<Hashtable<String, TTEntry>> transpositionTable;

    private final int INITIAL_HASHTABLE_SIZE = 100000;
    private int minAlpha = Integer.MIN_VALUE + 1;
    private int maxBeta = Integer.MAX_VALUE;
    private int maxDepth;
    private int currentLevel;
    private long visitedNodesCount;
    private boolean timeout = false;

    public TTAlphaBetaAlgorithm(int depth) {
	this.maxDepth = depth;
	if (depth > 0) {
	    this.transpositionTable = new ArrayList<Hashtable<String, TTEntry>>(
		    depth);
	    for (int i = 0; i < depth; ++i) {
		transpositionTable.add(i, new Hashtable<String, TTEntry>(
			INITIAL_HASHTABLE_SIZE));
	    }
	}
    }

    @Override
    public Move getNextMove(byte[][] boardState, byte player, long maxRunTime) {

	GameState currentState = new GameState(boardState);
	GameState newState;
	TTEntry testedEntry;
	ArrayList<Move> incompleteMovesList;
	ArrayList<Move> noKnowledgeMovesList = new ArrayList<Move>(
		(36 - currentState.getMarblesCount()) * 8);
	ArrayList<Move> realMovesList = new ArrayList<Move>(
		(36 - currentState.getMarblesCount()) * 8);
	ArrayList<GameState> noKnowledgeStatesList = new ArrayList<GameState>(
		(36 - currentState.getMarblesCount()) * 8);
	ArrayList<GameState> realStatesList = new ArrayList<GameState>(
		(36 - currentState.getMarblesCount()) * 8);
	Move nextMove = null;
	Move bestMove = null;
	Hashtable<String, TTEntry> lowestLevelTable = null;
	Watchman watchman = new Watchman(maxRunTime, this);
	int alpha = minAlpha;
	int beta = maxBeta;
	int score;

	currentLevel = currentState.getMarblesCount();
	visitedNodesCount = 0;
	timeout = false;
	// currentStates = new Hashtable(INITIAL_HASHTABLE_SIZE);
	if (maxDepth > 0) {
	    transpositionTable.remove(0);
	    if (maxDepth > 1) {
		transpositionTable.remove(0);
		transpositionTable.add(maxDepth - 2,
			new Hashtable<String, TTEntry>(INITIAL_HASHTABLE_SIZE));
	    }
	    transpositionTable.add(maxDepth - 1,
		    new Hashtable<String, TTEntry>(INITIAL_HASHTABLE_SIZE));
	    lowestLevelTable = transpositionTable.get(0);
	}

	incompleteMovesList = currentState.generateIncompleteMoves();
	for (Move move : incompleteMovesList) {
	    newState = currentState.nextStateFromMove(move);
	    if (newState.isTerminal()) {
		score = -newState.evaluate();
		if (score >= GameState.FIVE_IN_ROW_SCORE / 2) {
		    return move;						// Found finishing move
		}
	    }

	    for (int platePosIndex = 0; platePosIndex < PentagoUtils.platePositions.length; ++platePosIndex) {
		for (int rotationIndex = 0; rotationIndex < PentagoUtils.rotations.length; ++rotationIndex) {
		    try {
			nextMove = new Move(move.getPosition(),
				PentagoUtils.platePositions[platePosIndex],
				PentagoUtils.rotations[rotationIndex]);
		    } catch (PentagoInvalidPositionException
			    | PentagoInvalidRotationException
			    | PentagoInvalidPlatePositionException e) {
			e.printStackTrace();
		    }

		    newState = currentState.nextStateFromMove(nextMove);
		    if (newState.isTerminal()) {
			score = -newState.evaluate();
			if (score >= GameState.FIVE_IN_ROW_SCORE / 2) {
			    return nextMove;						// Found finishing move
			}
			if (score > alpha) {
			    alpha = score;
			    bestMove = nextMove;
			}
		    } else {
			if (maxDepth > 0) {
			    testedEntry = lowestLevelTable.get(newState
				    .generateHashKey());
			    if (testedEntry != null
				    && testedEntry.getScore() > alpha) {
				realMovesList.add(nextMove);
				realStatesList.add(newState);
			    } else {
				noKnowledgeMovesList.add(nextMove);
				noKnowledgeStatesList.add(newState);
			    }
			} else {
			    noKnowledgeMovesList.add(nextMove);
			    noKnowledgeStatesList.add(newState);
			}
		    }
		}
	    }
	}

	PentagoUtils.randomizeMovesStates(realMovesList, realStatesList);
	PentagoUtils.randomizeMovesStates(noKnowledgeMovesList,
		noKnowledgeStatesList);

	realMovesList.addAll(noKnowledgeMovesList);
	realStatesList.addAll(noKnowledgeStatesList);

	assert realMovesList.size() == realStatesList.size();

	watchman.start();

	GameState state;
	// String key;
	for (int i = 0; i < realMovesList.size(); ++i) {
	    state = realStatesList.get(i);
	    // key = state.generateHashKey();
	    // if (currentStates.containsKey(key)) {
	    // continue;
	    // }
	    score = -TTAlphaBeta(state, maxDepth, -beta, -alpha);

	    if (score >= GameState.FIVE_IN_ROW_SCORE / 2) {
		System.out
			.println("Visited nodes by TTAlpha-Beta for marble count of "
				+ currentState.getMarblesCount()
				+ ": "
				+ visitedNodesCount);
		return realMovesList.get(i);						// Found good path
	    }
	    if (score > alpha) {
		alpha = score;
		bestMove = realMovesList.get(i);
	    }
	    // insertState(state, score);
	    if (timeout)
		break;
	}

	watchman.shutdown();
	System.out.println("Visited nodes by TTAlpha-Beta for marble count of "
		+ currentState.getMarblesCount() + ": " + visitedNodesCount);

	return bestMove;
    }

    private int TTAlphaBeta(GameState state, int depth, int alpha, int beta) {
	if (depth == 0 || state.isTerminal() || timeout) {
	    ++visitedNodesCount;
	    return state.evaluate();
	}

	GameState nextState;
	int score;
	Move nextMove = null;
	Move bestMove = null;
	ArrayList<Move> incompleteMovesList;

	TTEntry previousStateScore = transpositionTable.get(maxDepth - depth)
		.get(state.generateHashKey());
	if (previousStateScore != null
		&& transpositionTable.get(maxDepth - depth).containsKey(
			state.generateHashKey())) {
	    if (previousStateScore.getEntryLevel() == currentLevel)
		return previousStateScore.getScore();
	    nextMove = previousStateScore.getBestMove();
	    if (nextMove != null) {
		nextState = state.nextStateFromMove(nextMove);
		score = -TTAlphaBeta(nextState, depth - 1, -beta, -alpha);
		if (score > alpha) {
		    alpha = score;
		    bestMove = nextMove;
		}
		if (alpha >= beta) {
		    insertState(state, beta, depth, bestMove);
		    return beta;
		}
	    }
	    // return (int) currentStates.get(state.generateHashKey());
	}

	++visitedNodesCount;
	incompleteMovesList = state.generateIncompleteMoves();

	for (Move move : incompleteMovesList) {
	    nextState = state.nextStateFromMove(move);
	    if (nextState.isTerminal()) {
		score = -TTAlphaBeta(nextState, depth - 1, -beta, -alpha);
		if (score > alpha) {
		    alpha = score;
		    bestMove = move;
		}
		if (alpha >= beta) {
		    insertUncertainState(state, beta, depth, bestMove);
		    return beta;
		}
		if (timeout)
		    break;
	    }
	}

	for (Move move : incompleteMovesList) {
	    if (timeout)
		break;
	    for (int platePosIndex = 0; platePosIndex < PentagoUtils.platePositions.length; ++platePosIndex) {
		if (timeout)
		    break;
		for (int rotationIndex = 0; rotationIndex < PentagoUtils.rotations.length; ++rotationIndex) {
		    if (timeout)
			break;
		    try {
			nextMove = new Move(move.getPosition(),
				PentagoUtils.platePositions[platePosIndex],
				PentagoUtils.rotations[rotationIndex]);
		    } catch (PentagoInvalidPositionException
			    | PentagoInvalidRotationException
			    | PentagoInvalidPlatePositionException e) {
			e.printStackTrace();
		    }

		    nextState = state.nextStateFromMove(nextMove);
		    score = -TTAlphaBeta(nextState, depth - 1, -beta, -alpha);
		    if (score > alpha) {
			alpha = score;
			bestMove = nextMove;
		    }
		    if (alpha >= beta) {
			insertUncertainState(state, beta, depth, bestMove);
			return beta;
		    }

		}
	    }
	}

	// ArrayList<GameState> nextStates = PentagoUtils.TTGenerateNextStates(
	// state, currentStates);
	//
	// for (GameState s : nextStates) {
	// score = -TTAlphaBeta(s, depth - 1, -beta, -alpha);
	// if (score > alpha) {
	// alpha = score;
	// bestMove = nextMove;
	// }
	// if (alpha >= beta)
	// return beta;
	// if (timeout)
	// break;
	// }

	insertState(state, alpha, depth, bestMove);
	return alpha;
    }

    // private boolean stateExists(GameState state) {
    // return currentStates.containsKey(state.generateHashKey());
    // }

    private void insertState(GameState state, int score, int depth,
	    Move bestMove) {
	String key = state.generateHashKey();
	transpositionTable.get(maxDepth - depth).remove(key);
	transpositionTable.get(maxDepth - depth).put(key,
		new TTEntry(score, bestMove, currentLevel));
	// currentStates.put(state.generateHashKey(), score);
    }

    private void insertUncertainState(GameState state, int score, int depth,
	    Move bestMove) {
	String key = state.generateHashKey();
	transpositionTable.get(maxDepth - depth).remove(key);
	transpositionTable.get(maxDepth - depth).put(key,
		new TTEntry(score, bestMove, currentLevel - 1));
	// currentStates.put(state.generateHashKey(), score);
    }

    @Override
    public void executeTimeout() {
	timeout = true;
    }

}
